In high performance distributed computing, a network must have high throughput, low latency, and graceful degradation under heavy workloads. In addition, high performance distributed computing must have the ability to provide guaranteed performance to real-time applications, and performance that is both fair and predictable. A barrier to building high performance networks is the difficulty of high speed switching--of taking data arriving on an input link and quickly sending it out an appropriate output link. The switching task is simplified if the data can be processed in fixed length cells.
Many high speed switch architectures use the same hardware for both scheduling and forwarding. If the input and output links of a switch are connected internally by a multi-stage interconnection network, the internal network can detect and resolve conflicts between cells as they work their way through the switch.
As is also well known in the art, current methods to schedule conversation requests to an open channel work fine with any implementation of a slotted network medium as long as there are n channels and n users. A slotted communications medium is a synchronous medium that is logically divided into time frames. Each time frame is further divided into a fixed number of slots, and each slot contains a fixed number of channels. Where the number of users and the number of channels are equal, no problem usually exists; designers will use scheduling methods well known in the art, such as the Slepian-Duguid method. However, a scheduling method is needed when the number of users exceeds the number of channels on a slotted medium, and where, in a frame, (1) a first slot with a transmitter portion of a transmitter-receiver pair is free, and (2) a second slot with a receiver portion of the transmitter-receiver pair is free, and (3) a free channel is free in a third slot.